, its time to consider using a different way of imaging
objects. One such way is image based rendering family of methods.
The method I prefer is called Layered Depth
Images (Microsoft
research-graphics pubs, year 1998) , with a modification that it is
used to describe a bounded volume instead of an infinitly high pyramid.
The basic idea is to store the surface pixels as an array of records (x,
y, z, color, normal), of course modified to exploit the space coherency
of such data. When it comes to drawing, you project the object pixel by
pixel to the new position. It isn's as hard as it looks.
Some details
Handling occlusion artifacts
The image is represented as an array of pixels,
as would be seen from a certain point, the "original center of projection
(COP)". Every pixel stores a color value, and a function of the pixel's
depth, called "disparity". This image can be 3D-warped to show scene from
any viewpoint. This is a classical approach, mentioned by McMillan in his
Ph.D. thesis (has been removed).
It produces good images, but they show two types of artifacts: a) a solid
surface may show cracks, through which you can see the background; b) surfaces
that weren't seen from the original COP won't be present in the output
image at all - it is called "occlusion artifacts". The occlusion artifacts
can be handled by storing not only the pixels visible from the COP, but
all pixels that could possibly be seen while wieving. It requires storing
multiple (color, disparity, normal) records per pixel. It can be done without
wasting memory using a depth-counter and a pointer for every pixel; the
pointer points to a table containing all the pixels of the image.
This is what is called Layered Depth Image.
Handling cracks
Using this method, the occlusion artifacts
are removed. However, the are still small cracks in solid surfaces, due
to rounding errors and the fact that a certain surface can be magnified
in a certain view, causing undersampling. For other techniques, this can
be avoided using backward mapping. However, backward mapping for 3D-warp
requires searching a line for every pixel, which is too expensive. So,
this is what the normal is used for: for every pixel, you compute the size
of the projected pixel, and if it is too large, you fill a larger area
with the same color. As explained later, it is posible to reduce the area
filling routine to only two cases: area 1x1 and 3x3.
Speeding it up
Now its time to explain how it is ensured that
lower levels of image do not hide the foreground, when there is no z-buffering
nor sorting. It is ensured by a clever traversing through the source image.
An intersection of original-image plane and the line going through original
COP and new COP is called "epipole". You can assign it original-pixel coordinates
rather easily. Then, if the original COP is between the epipole and the
new COP, any traversing of the source image can be used, with only one
condition: when you warp a pixel, all pixels on the line between this pixel
and the epipole must have been already warped. It results in going from
the epipole to the edges. With this, it is ensured that pixels arrive in
back-to-front order, thus you can simply write the pixels and visibility
would be handled correctly. For LDI, there is one more condition: pixels
in the same position must be traversed back-to-front, which is easily done
by storing them in such order.
If the new COP is between the original
COP and the epipole, or the epipole is between the COPs, the traversing
is similar, but the condition is "no pixel between the warped pixel and
the epipole must have been warped". It means you go from the edges to the
epipole.
Typically, the original image is divided
to 4 axis-aligned sheets, with a common corner at the epipole. Every sheet
is then traversed row-by-row, with left-to-right or vice versa, and from
top to bottom or vice versa, as required by the warping condition.
The equation that takes the pixels of the
original image and computes new pixel positions, is called "warping equation"
and looks like this:
Ax+By+C+D§
Ix+Jy+K+L§
xnew = ----------, ynew = -----------, where
"§" substitutes greek "delta" and means disparity (I haven't found
"delta" in HTML).
Ex+Fy+G+H§
Ex+Fy+G+H§
When visiting a pixel, you set the x and y, go through the §s
in the source image, then moving to the next x. It looks cheap, with only
3 additions per pixel and 5 muls, 3 adds and 1 reciprocal per depth level
and pixel. The row setup time isn't very important. But, the equations
can be rearranged (if H <> 0) as this:
ax+by+c
ix+jy+k
xnew = m + ----------, ynew = n + ----------,
ex+fy+g+§
ex+fy+g+§
requiring 3 additions per pixel and 2 muls, 4 additions and 1 reciprocal
per depth level and pixel. Further playing with the equations, it is possible
to reach this:
ax+by+c
1
ix+jy+k 1
xnew = m + -------- ------------, ynew =
n + -------- ------------,
ex+fy+g
1+§/(ex+fy+g)
ex+fy+g 1+§/(ex+fy+g)
If we limit § not to be too high, ensure that abs(ex+fy+g)
is large enough and we do not divide the source image by lines that are
axis-aligned, but by line with constant ex+fy+g and the line perpendicular
to this one, thus having ex+fy+g constant through the row, we need only
2 adds per pixel and 3 muls, 2 adds and 1 L2 cache lookup (for 1/(1+x),
with x in a limited interval, using about 16 bits).
-------------
To be rewritten and continued.
Up: The Advanced Projects Page
Last revised on September 22, 1998.
Last modified on September 22, 1998, at 21:39.